package pers.vic.basics.leetcode;

import java.util.Arrays;

/**
 * @description: 75. 颜色分类 {@literal https://leetcode-cn.com/problems/sort-colors/}
 * @author Vic.xu
 * @date: 2021/1/11 0011 8:56
 */
public class J0075_M_SortColors {
    /*
    给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
    此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

    进阶：
    你可以不使用代码库中的排序函数来解决这道题吗？
    你能想出一个仅使用常数空间的一趟扫描算法吗？
     */
    public static void sortColors(int[] nums) {
        int len = nums.length;
        if (len <= 1) {
            return;
        }
        int left = 0;
        int right = len - 1;
        /*
          1. 把1 往前排  把2往后排，已排好的不用重新排
          2. 交换位置后需要再次处理当前位置的颜色，所以 不往前++
         */
        for (int i = 0; i <= right; ) {
            int cur = nums[i];
            if (cur == 0 && i != left) {
                swap(nums, i, left++);
            }else if (cur == 2 && i != right) {
                swap(nums, i, right--);
            }else {
                i++;
            }
        }
    }

    private static void swap(int[] nums, int s, int t){
        int temp = nums[s];
        nums[s] = nums[t];
        nums[t] = temp;
    }

    public static void main(String[] args) {
        int[] nums = {2,0,2,1,1,2,1,0};
        sortColors(nums);
        System.out.println(Arrays.toString(nums));

        int[] nums2 = {1,2,0};
        sortColors(nums2);
        System.out.println(Arrays.toString(nums2));
    }
}
